{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Increasing Path in a Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort #memoization #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序 #记忆化搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestIncreasingPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中的最长递增路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <code>m x n</code> 整数矩阵 <code>matrix</code> ，找出其中 <strong>最长递增路径</strong> 的长度。</p>\n",
    "\n",
    "<p>对于每个单元格，你可以往上，下，左，右四个方向移动。 你 <strong>不能</strong> 在 <strong>对角线</strong> 方向上移动或移动到 <strong>边界外</strong>（即不允许环绕）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/05/grid1.jpg\" style=\"width: 242px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[9,9,4],[6,6,8],[2,1,1]]\n",
    "<strong>输出：</strong>4 \n",
    "<strong>解释：</strong>最长递增路径为 <code>[1, 2, 6, 9]</code>。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/27/tmp-grid.jpg\" style=\"width: 253px; height: 253px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[3,4,5],[3,2,6],[2,2,1]]\n",
    "<strong>输出：</strong>4 \n",
    "<strong>解释：</strong>最长递增路径是 <code>[3, 4, 5, 6]</code>。注意不允许在对角线方向上移动。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[1]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 200</code></li>\n",
    "\t<li><code>0 <= matrix[i][j] <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-increasing-path-in-a-matrix](https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-increasing-path-in-a-matrix](https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[9,9,4],[6,6,8],[2,1,1]]', '[[3,4,5],[3,2,6],[2,2,1]]', '[[1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        len_r=len(matrix)\n",
    "        len_c=len(matrix[0])        \n",
    "        res=[[0 for _ in range(len_c)] for _ in range(len_r)]        \n",
    "        #print('res1',res1)\n",
    "        dis=[[-1,0],[0,-1],[1,0],[0,1]]\n",
    "        lt=0\n",
    "        for nr in range(len_r):\n",
    "            for nc in range(len_c):                                \n",
    "                lt=max(lt,self.dfs(matrix,nr,nc,dis,res))                        \n",
    "        return lt\n",
    "\n",
    "    def dfs(self,matrix,nr,nc,dis,res):\n",
    "        if res[nr][nc] != 0:\n",
    "            return res[nr][nc]\n",
    "        ct=1\n",
    "        for i in dis:\n",
    "            x,y=nr+i[0],nc+i[1]\n",
    "            flag= x>=0 and x<len(matrix) and y>=0 and y<len(matrix[0])\n",
    "            if flag and matrix[nr][nc]<matrix[x][y]:                                \n",
    "                ct=max(ct,1+self.dfs(matrix,x,y,dis,res))                                \n",
    "        res[nr][nc]=ct\n",
    "        #print(res)\n",
    "        return ct\n",
    "'''\n",
    "if __name__==\"__main__\":\n",
    "    inputstr=input()\n",
    "    matrix=[x.replace(']','').split(',') for x in inputstr.replace('[','').split('],')]\n",
    "    for i in range(len(matrix)):\n",
    "        for j in range(len(matrix[i])):\n",
    "            matrix[i][j]=int(matrix[i][j])\n",
    "    #print(matrix)\n",
    "    a=Solution()\n",
    "    print(a.longestIncreasingPath(matrix))\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        col = len(matrix)\n",
    "        row = len(matrix[0])\n",
    "\n",
    "        dp = [[0 for _ in range(row)] for _ in range(col)]\n",
    "        \n",
    "        answer = 1\n",
    "\n",
    "        for x in range(col):\n",
    "            for y in range(row):\n",
    "                if dp[x][y] == 0:\n",
    "                    self.dfs(col, row, x, y, matrix, dp)\n",
    "                    answer = max(answer, dp[x][y])\n",
    " \n",
    "        return answer\n",
    "    \n",
    "    def inofboard(self, col, row, i, j):\n",
    "        if 0 <= i < col and 0 <= j < row:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def bigger(self, col, row, x, y, i, j, matrix):\n",
    "        if self.inofboard(col, row, i, j) and matrix[x][y] > matrix[i][j]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def dfs(self, col, row, i, j, matrix, dp):\n",
    "        dp[i][j] = 1\n",
    "        for k, l in ((1, 0), (0, 1), (-1, 0), (0, -1)):\n",
    "            if self.bigger(col, row, i, j, i+k, j+l, matrix):\n",
    "                if dp[i+k][j+l] == 0:\n",
    "                    self.dfs(col, row, i+k, j+l, matrix, dp)\n",
    "                dp[i][j] = max(dp[i][j], dp[i+k][j+l]+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        dp = [[0 for j in range(len(matrix[0]))] for i in range(len(matrix))]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                ans = max(ans, self.process2(matrix, i, j, dp))\n",
    "        return ans\n",
    "\n",
    "    def process2(self, matrix, i, j, dp):\n",
    "        # if i < 0 or i >= len(matrix) or j < 0 or j >= len(matrix[0]):\n",
    "        #     return -1\n",
    "        if dp[i][j] != 0:\n",
    "            return dp[i][j]\n",
    "        up = 0\n",
    "        down = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        if i - 1 >= 0 and matrix[i - 1][j] > matrix[i][j]:\n",
    "            up = self.process2(matrix, i - 1, j, dp)\n",
    "        if i + 1 < len(matrix) and matrix[i + 1][j] > matrix[i][j]:  # 4个方向都去走一遍\n",
    "            down = self.process2(matrix, i + 1, j, dp)\n",
    "        if j - 1 >= 0 and matrix[i][j - 1] > matrix[i][j]:\n",
    "            left = self.process2(matrix, i, j - 1, dp)\n",
    "        if j + 1 < len(matrix[0]) and matrix[i][j + 1] > matrix[i][j]:\n",
    "            right = self.process2(matrix, i, j + 1, dp)\n",
    "        dp[i][j] = 1 + max(up, down, left, right)\n",
    "        return dp[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dx = [-1, 1, 0, 0]\n",
    "        self.dy = [0, 0, -1, 1]\n",
    "        \n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        self.m, self.n = len(matrix), len(matrix[0])\n",
    "        self.f = [[-1 for _ in range(self.n)] for _ in range(self.m)]\n",
    "        res = 0\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                res = max(res, self.dp(i, j, matrix))\n",
    "        return res \n",
    "\n",
    "    def dp(self, x, y, matrix):\n",
    "        if self.f[x][y] != -1:return self.f[x][y]\n",
    "        self.f[x][y] = 1\n",
    "        for i in range(4):\n",
    "            a = x + self.dx[i]\n",
    "            b = y + self.dy[i]\n",
    "            if 0 <= a < self.m and 0 <= b < self.n and matrix[a][b] < matrix[x][y]:\n",
    "                self.f[x][y] = max(self.f[x][y], self.dp(a, b, matrix)+1)\n",
    "        return self.f[x][y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    \n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(row, column):\n",
    "        #     best = 1\n",
    "        #     for dx, dy in dirs:\n",
    "        #         new_row = row + dx\n",
    "        #         new_col = column + dy\n",
    "        #         if 0<= new_row < rows and 0<= new_col < columns and matrix[new_row][new_col] > matrix[row][column]:\n",
    "        #             best = max(best, dfs(new_row, new_col) + 1)\n",
    "        #     return best\n",
    "        \n",
    "        # ans = 0\n",
    "        # for i in range(rows):\n",
    "        #     for j in range(columns):\n",
    "        #         ans = max(ans, dfs(i, j))\n",
    "        \n",
    "        # return ans\n",
    "\n",
    "        outdegrees = [[0] * columns for _ in range(rows)]\n",
    "        queue = collections.deque()\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                for dx, dy in dirs:\n",
    "                    new_row = i + dx\n",
    "                    new_col = j + dy\n",
    "                    if 0<= new_row < rows and 0<= new_col < columns and matrix[new_row][new_col] > matrix[i][j]:\n",
    "                        outdegrees[i][j] += 1\n",
    "                if outdegrees[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            ans += 1\n",
    "            size = len(queue)\n",
    "            for _ in range (size):\n",
    "                row, col = queue.popleft()\n",
    "                for dx, dy in dirs:\n",
    "                    new_row = row + dx\n",
    "                    new_col = col + dy\n",
    "                    if 0<= new_row < rows and 0<= new_col < columns and matrix[new_row][new_col] < matrix[row][col]:\n",
    "                        outdegrees[new_row][new_col] -= 1\n",
    "                        if outdegrees[new_row][new_col] == 0:\n",
    "                            queue.append((new_row, new_col))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        \n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "        outdegrees = [[0] * columns for _ in range(rows)]\n",
    "        queue = collections.deque()\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                for dx, dy in Solution.DIRS:\n",
    "                    newRow, newColumn = i + dx, j + dy\n",
    "                    if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] < matrix[i][j]:\n",
    "                        outdegrees[i][j] += 1\n",
    "                if outdegrees[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            ans += 1\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                row, column = queue.popleft()\n",
    "                for dx, dy in Solution.DIRS:\n",
    "                    newRow, newColumn = row + dx, column + dy\n",
    "                    if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[row][column]:\n",
    "                        outdegrees[newRow][newColumn] -= 1\n",
    "                        if outdegrees[newRow][newColumn] == 0:\n",
    "                            queue.append((newRow, newColumn))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "       # graph: topological sort\n",
    "        m , n = len(matrix), len(matrix[0])\n",
    "        outdegress = [[0]*n for _ in range(m)]\n",
    "        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        queue = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x,y in direct:\n",
    "                    nei_x, nei_y = i+x, j+y\n",
    "                    if 0 <= nei_x < m and 0 <= nei_y < n and matrix[i][j] < matrix[nei_x][nei_y]:\n",
    "                        outdegress[i][j] += 1\n",
    "                if outdegress[i][j] == 0:\n",
    "                    queue.append([i,j])\n",
    "        res = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                i ,j = queue.pop(0)\n",
    "                for x,y in direct:\n",
    "                    nei_x, nei_y = i+x, j+y\n",
    "                    if 0 <= nei_x < m and 0 <= nei_y < n and matrix[i][j] > matrix[nei_x][nei_y]:\n",
    "                        outdegress[nei_x][nei_y] -= 1\n",
    "                        if outdegress[nei_x][nei_y] == 0:\n",
    "                            queue.append([nei_x, nei_y])\n",
    "            res += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix: return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        memo = [[0] * n for _ in range(m)]\n",
    "        def dfs(x: int, y: int):\n",
    "            if memo[x][y] != 0: return memo[x][y]\n",
    "            memo[x][y] += 1\n",
    "            for new_x, new_y in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if 0 <= new_x < m and 0 <= new_y < n and matrix[new_x][new_y] > matrix[x][y]:\n",
    "                    memo[x][y] = max(memo[x][y], dfs(new_x, new_y) + 1)\n",
    "            return memo[x][y]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        flag = [[-1]*n for _ in range(m)]\n",
    "        def dfs(i,j):\n",
    "            if flag[i][j] != -1:\n",
    "                return flag[i][j]\n",
    "            else:\n",
    "                deep =1\n",
    "                for (x,y) in ((-1,0),(1,0),(0,1),(0,-1)):\n",
    "                    x,y = i+x,j+y\n",
    "                    if 0<=x<m and 0<=y<n and matrix[x][y]>matrix[i][j]:\n",
    "                        deep=max(deep,dfs(x,y)+1)\n",
    "                flag[i][j] = deep\n",
    "                return deep\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if flag[i][j]==-1:\n",
    "                    res = max(res,dfs(i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "\n",
    "        h,w = len(matrix),len(matrix[0])\n",
    "\n",
    "        store = [[None]*(w) for i in range(h)]\n",
    "\n",
    "        ans = 0\n",
    "        def search_nearby(i,j):\n",
    "            compare = [] #储存可以比较的候选人\n",
    "            #上\n",
    "\n",
    "            if i != 0 and matrix[i-1][j] < matrix[i][j]: #有上边且上边小于当前数的话\n",
    "                compare.append(store[i-1][j]) if store[i-1][j] else compare.append(search_nearby(i-1,j))\n",
    "\n",
    "            #左\n",
    "            if j != 0 and matrix[i][j-1] < matrix[i][j]: #有左边且左边小于当前数的话\n",
    "                compare.append(store[i][j-1]) if store[i][j-1] else compare.append(search_nearby(i,j-1))\n",
    "\n",
    "            #下\n",
    "            if i != h-1 and matrix[i+1][j] < matrix[i][j]: #有下边且下边小于当前数的话\n",
    "                compare.append(store[i+1][j]) if store[i+1][j] else compare.append(search_nearby(i+1,j))\n",
    "\n",
    "            #右\n",
    "            if j != w-1 and matrix[i][j+1] < matrix[i][j]: #有右边且右边小于当前数的话\n",
    "                compare.append(store[i][j+1]) if store[i][j+1] else compare.append(search_nearby(i,j+1))\n",
    "            \n",
    "            store[i][j] = max(compare)+1 if compare else 1\n",
    "\n",
    "            return (store[i][j])\n",
    "        \n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if not store[i][j]:\n",
    "                    ans = max(ans, search_nearby(i,j))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        h, w = len(matrix), len(matrix[0])\n",
    "\n",
    "        store = [[None] * w for _ in range(h)]\n",
    "\n",
    "        m = 0\n",
    "\n",
    "        def search_nearby(i, j):\n",
    "            nonlocal m\n",
    "\n",
    "            compare = []\n",
    "\n",
    "            directions = [\n",
    "                (-1, 0),\n",
    "                (0, -1),\n",
    "                (1, 0),\n",
    "                (0, 1),\n",
    "            ]\n",
    "\n",
    "            conditions = [\n",
    "                i != 0,\n",
    "                j != 0,\n",
    "                i != h-1,\n",
    "                j != w-1\n",
    "            ]\n",
    "            \n",
    "            for index, (dx, dy) in enumerate(directions):\n",
    "                nx = i+dx\n",
    "                ny = j+dy\n",
    "                if conditions[index] and matrix[i][j] > matrix[nx][ny]:\n",
    "                    compare.append(store[nx][ny]) if store[nx][ny] else compare.append(search_nearby(nx,ny))\n",
    "\n",
    "            store[i][j] = max(compare) + 1 if compare else 1\n",
    "            m = max(m, store[i][j])\n",
    "            return store[i][j]\n",
    "        \n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if not store[i][j]:\n",
    "                    search_nearby(i,j)\n",
    "\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if memo[i][j] != 0:\n",
    "                return memo[i][j]\n",
    "            val = matrix[i][j]\n",
    "            memo[i][j] = 1 + max(\n",
    "                dfs(i - 1, j) if i > 0 and val < matrix[i - 1][j] else 0,\n",
    "                dfs(i + 1, j) if i < M - 1 and val < matrix[i + 1][j] else 0,\n",
    "                dfs(i, j - 1) if j > 0 and val < matrix[i][j - 1] else 0,\n",
    "                dfs(i, j + 1) if j < N - 1 and val < matrix[i][j + 1] else 0)\n",
    "            return memo[i][j]\n",
    "\n",
    "        M, N = len(matrix), len(matrix[0])\n",
    "        memo = [[0] * N for _ in range(M)]\n",
    "        return max(dfs(x, y) for x in range(M) for y in range(N))\n",
    "                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dp_check = [[False for _ in range(n)] for _ in range(m)]\n",
    "        ret = 0\n",
    "        def get(x,y):\n",
    "            nonlocal ret\n",
    "            if dp_check[x][y]:\n",
    "                return \n",
    "            neighbour = 0\n",
    "            check = False\n",
    "            for (i,j) in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
    "                if 0<=x+i<m and 0<=y+j<n:\n",
    "                    if matrix[x+i][y+j]<matrix[x][y]:\n",
    "                        check = True\n",
    "                        if not dp_check[x+i][y+j]:\n",
    "                            get(x+i,y+j)\n",
    "                        neighbour = max(neighbour,dp[x+i][y+j])\n",
    "\n",
    "            dp[x][y] = neighbour + 1\n",
    "            dp_check[x][y] = True\n",
    "            ret = max(ret,dp[x][y])\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                get(x,y)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dp = [[1 for _ in range(n)] for p in range(m)]\n",
    "        sortednum = sorted(sum([[(matrix[i][j],i,j) for j in range(n) for i in range(m)]],[]))\n",
    "        for v,k,l in sortednum:\n",
    "            dp[k][l] = 1+max( dp[k-1][l] if k and v>matrix[k-1][l] else 0,\n",
    "                              dp[k+1][l] if k<=m-2 and v>matrix[k+1][l] else 0,\n",
    "                              dp[k][l+1] if l<=n-2 and v>matrix[k][l+1] else 0,\n",
    "                              dp[k][l-1] if l and v>matrix[k][l-1] else 0,                                        \n",
    "            )\n",
    "            res = max(res,dp[k][l])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 深度优先搜索。使用二维数组 record 存储遍历过的单元格最大路径长度，已经遍历过的单元格就不需要再次遍历了。\n",
    "class Solution:\n",
    "    max_len = 0\n",
    "    directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        record = [[0 for _ in range(cols)] for _ in range(rows)]\n",
    "        def dfs(i, j):\n",
    "            record[i][j] = 1\n",
    "            for direction in self.directions:\n",
    "                new_i, new_j = i + direction[0], j + direction[1]\n",
    "                if 0 <= new_i < rows and 0 <= new_j < cols and matrix[new_i][new_j] > matrix[i][j]:\n",
    "                    if record[new_i][new_j] == 0:\n",
    "                        dfs(new_i, new_j)\n",
    "                    record[i][j] = max(record[i][j], record[new_i][new_j] + 1)\n",
    "            self.max_len = max(self.max_len, record[i][j])\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if record[i][j] == 0:\n",
    "                    dfs(i, j)\n",
    "        return self.max_len\n",
    "\n",
    "# 动态优化dp[i][j]表示以matrix[i][j]结尾的最长递增长度\n",
    "# 先预处理，对矩阵的值按从小到大排序，按大小顺序才能保证依赖的子问题都求解过了\n",
    "# 之所以要先排序，我觉得很可能是因为倒数第二行dp[i][j]=max(dp[i][j],1+dp[r][c])。 这里出现了dp[r][c]，所以我们在计算dp[i][j]之前，必须先把dp[r][c]计算出来。 matrix(r,c)位置的值比matrix（i，j）位置的值小（从if语句看出来的）。所以我们只要保证，先把matrix中值小的位置的dp先算出来，再把值大的位置的dp算出来，倒数第二行的代码就有意义了。所以我们要先排序。\n",
    "class Solution(object):\n",
    "    def longestIncreasingPath(self, matrix):\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        lst = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                lst.append((matrix[i][j], i, j))\n",
    "        lst.sort()  # 用是优先队列就省去sort\n",
    "        dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "        ans = -1\n",
    "        for num, i, j in lst:\n",
    "            # dp[i][j] = 1\n",
    "            for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n",
    "                r, c = i + di, j + dj\n",
    "                if 0 <= r < m and 0 <= c < n:\n",
    "                    if matrix[i][j] > matrix[r][c]:\n",
    "                        dp[i][j] = max(dp[i][j], 1 + dp[r][c])\n",
    "            ans = max(ans, dp[i][j])\n",
    "        # return max([dp[i][j] for i in range(m) for j in range(n)])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Takeaway\n",
    "# 1. 不需要onPath，只有在cycle出现的时候才要。因为strictly increasing，是不可能掉头的\n",
    "# 2. \n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        visited = [ [0] * n for _ in range(m)]\n",
    "        onPath = [ [False] * n for _ in range(m)]\n",
    "        def dfs(r, c): \n",
    "            \"\"\"\n",
    "            return the longest increasing path starting here\n",
    "            \"\"\"\n",
    "            if visited[r][c] != 0: return visited[r][c]\n",
    "            # if onPath[r][c]: return -float('inf')\n",
    "\n",
    "            # onPath[r][c] = True\n",
    "            cnt = 1\n",
    "            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: \n",
    "                nr, nc = r + dr, c + dc\n",
    "                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]: \n",
    "                    cnt = max(dfs(nr, nc) + 1, cnt)\n",
    "            \n",
    "            # onPath[r][c] = False\n",
    "            visited[r][c] = max(visited[r][c], cnt)\n",
    "            return cnt\n",
    "        \n",
    "        max_cnt = 0\n",
    "        for r in range(m): \n",
    "            for c in range(n): \n",
    "                max_cnt = max(dfs(r, c), max_cnt)\n",
    "        print(visited)\n",
    "        return max_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        pos = list((i, j) for i in range(n) for j in range(m))\n",
    "        ans = 1\n",
    "        dp = [[1] * m for _ in range(n)]\n",
    "        pos.sort(key = lambda x: matrix[x[0]][x[1]])\n",
    "        for i, j in pos:\n",
    "            for ni, nj in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):\n",
    "                if ni < 0 or ni >= n or nj < 0 or nj >= m or matrix[ni][nj] <= matrix[i][j]:\n",
    "                    continue\n",
    "                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + 1)\n",
    "            ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        visited = [ [0] * n for _ in range(m)]\n",
    "        onPath = [ [False] * n for _ in range(m)]\n",
    "        def dfs(r, c): \n",
    "            \"\"\"\n",
    "            return the longest increasing path starting here\n",
    "            \"\"\"\n",
    "            if visited[r][c] != 0: return visited[r][c]\n",
    "            if onPath[r][c]: return -float('inf')\n",
    "\n",
    "            onPath[r][c] = True\n",
    "            cnt = 1\n",
    "            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]: \n",
    "                nr, nc = r + dr, c + dc\n",
    "                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]: \n",
    "                    cnt = max(dfs(nr, nc) + 1, cnt)\n",
    "            \n",
    "            onPath[r][c] = False\n",
    "            visited[r][c] = max(visited[r][c], cnt)\n",
    "            return cnt\n",
    "        \n",
    "        max_cnt = 0\n",
    "        for r in range(m): \n",
    "            for c in range(n): \n",
    "                max_cnt = max(dfs(r, c), max_cnt)\n",
    "        print(visited)\n",
    "        return max_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        OFFSET = [[-1,0],[1,0],[0,-1],[0,1]]\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        length = [[0]*col for _ in range(row)]\n",
    "        visited = [[False]*col for _ in range(row)]\n",
    "        @lru_cache\n",
    "        def dfs(i,j):\n",
    "            if visited[i][j]:\n",
    "                return length[i][j]\n",
    "            max_length = 0\n",
    "            for index in OFFSET:\n",
    "                next_i = i+index[0]\n",
    "                next_j = j+index[1]\n",
    "                if (next_i>=0 and next_i<row) and (next_j>=0 and next_j<col):\n",
    "                    if matrix[next_i][next_j] > matrix[i][j]:\n",
    "                        max_length = max(max_length,dfs(next_i,next_j))\n",
    "            visited[i][j] = True\n",
    "            length[i][j] = max_length+1\n",
    "            return length[i][j]\n",
    "        ans = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                ans = max(ans,dfs(i,j))\n",
    "        return ans\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix):\n",
    "        if not matrix: \n",
    "            return 0\n",
    "        self.directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        self.memo = {}\n",
    "        self.matrix = matrix\n",
    "        self.max_length = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                self.max_length = max(self.max_length, self.dfs(i, j))\n",
    "        return self.max_length\n",
    "\n",
    "    def dfs(self, i, j):\n",
    "        if (i, j) in self.memo:\n",
    "            return self.memo[(i, j)]\n",
    "        length = 1\n",
    "        for dx, dy in self.directions:\n",
    "            x, y = i + dx, j + dy\n",
    "            if x < 0 or x >= len(self.matrix) or y < 0 or y >= len(self.matrix[0]) or self.matrix[x][y] <= self.matrix[i][j]:\n",
    "                continue\n",
    "            length = max(length, 1 + self.dfs(x, y))\n",
    "        self.memo[(i, j)] = length\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestIncreasingPath(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.directions = [[-1, 0], [1, 0], [0, -1], [0,1]]\n",
    "        self.pathLenDict = {}\n",
    "        max_len = float(\"-inf\")\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                cur_len = self.longestPath(i, j, matrix)\n",
    "                if cur_len > max_len:\n",
    "                    max_len = cur_len\n",
    "        return max_len\n",
    "\n",
    "\n",
    "\n",
    "    def longestPath(self, i, j, matrix):\n",
    "        k = \"{}_{}\".format(i, j) \n",
    "\n",
    "        if k in self.pathLenDict:\n",
    "            return self.pathLenDict[k]\n",
    "\n",
    "        max_path = 1\n",
    "        for direction in self.directions:\n",
    "            new_i = i + direction[0]\n",
    "            new_j = j + direction[1]\n",
    "            if new_i >= 0 and new_i < len(matrix) and new_j >=0 and new_j < len(matrix[0]) and matrix[new_i][new_j] > matrix[i][j]:\n",
    "                pathLen = 1 + self.longestPath(new_i, new_j, matrix)\n",
    "                if pathLen > max_path:\n",
    "                    max_path = pathLen\n",
    "        \n",
    "        self.pathLenDict[k] = max_path\n",
    "        return max_path\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dp = {}\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, self.dfs(i,j, matrix, dp))\n",
    "                # print(i,j,matrix[i][j], dp)\n",
    "        return res\n",
    "                \n",
    "\n",
    "    def dfs(self, i, j, matrix, dp): \n",
    "        if i==len(matrix) or j==len(matrix[0]):\n",
    "            return 0\n",
    "        up, down, left, right = 0,0,0,0\n",
    "        if i-1>=0 and matrix[i][j] < matrix[i-1][j]:\n",
    "            if (i-1, j) in dp:\n",
    "                up = dp[(i-1, j)]\n",
    "            else:\n",
    "                up = self.dfs(i-1, j, matrix, dp)\n",
    "                dp[(i-1, j)] = up\n",
    "        if i+1<len(matrix) and matrix[i][j] < matrix[i+1][j]:\n",
    "            if (i+1, j) in dp:\n",
    "                down = dp[(i+1, j)]\n",
    "            else:\n",
    "                down = self.dfs(i+1, j, matrix, dp)\n",
    "                dp[(i+1, j)] = down\n",
    "        if j-1>=0 and matrix[i][j] < matrix[i][j-1]:\n",
    "            if (i, j-1) in dp:\n",
    "                left = dp[(i, j-1)]\n",
    "            else:\n",
    "                left = self.dfs(i, j-1, matrix, dp)\n",
    "                dp[(i, j-1)] = left\n",
    "        if j+1<len(matrix[0]) and matrix[i][j] < matrix[i][j+1]:\n",
    "            if (i, j+1) in dp:\n",
    "                right = dp[(i, j+1)]\n",
    "            else:\n",
    "                right = self.dfs(i, j+1, matrix, dp)\n",
    "                dp[(i, j+1)] = right\n",
    "        res = max([up, down, left, right])+1\n",
    "        dp[(i,j)] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        degree = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        link = [[[] for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j != n-1:\n",
    "                    if matrix[i][j] > matrix[i][j+1]:\n",
    "                        degree[i][j] += 1\n",
    "                        link[i][j+1].append(i*n + j)\n",
    "                    elif  matrix[i][j] < matrix[i][j+1]:\n",
    "                        degree[i][j+1] += 1\n",
    "                        link[i][j].append(i*n + j + 1)\n",
    "                if i != m-1:\n",
    "                    if matrix[i][j] > matrix[i+1][j]:\n",
    "                        degree[i][j] += 1\n",
    "                        link[i+1][j].append(i*n + j)\n",
    "                    elif  matrix[i][j] < matrix[i+1][j]:\n",
    "                        degree[i+1][j] += 1\n",
    "                        link[i][j].append(i*n + j + n)\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if degree[i][j] == 0:\n",
    "                    search = link[i][j]\n",
    "                    d = 1\n",
    "                    while search:\n",
    "                        temp = []\n",
    "                        for idxencode in search:\n",
    "                            x = idxencode // n\n",
    "                            y = idxencode % n\n",
    "                            for enco in link[x][y]:\n",
    "                                temp.append(enco)\n",
    "                        search = list(set(temp))\n",
    "                        d += 1\n",
    "                    ans = max(ans, d)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        degree = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        link = [[[] for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j != n-1:\n",
    "                    if matrix[i][j] > matrix[i][j+1]:\n",
    "                        degree[i][j] += 1\n",
    "                        link[i][j+1].append(i*n + j)\n",
    "                    elif  matrix[i][j] < matrix[i][j+1]:\n",
    "                        degree[i][j+1] += 1\n",
    "                        link[i][j].append(i*n + j + 1)\n",
    "                if i != m-1:\n",
    "                    if matrix[i][j] > matrix[i+1][j]:\n",
    "                        degree[i][j] += 1\n",
    "                        link[i+1][j].append(i*n + j)\n",
    "                    elif  matrix[i][j] < matrix[i+1][j]:\n",
    "                        degree[i+1][j] += 1\n",
    "                        link[i][j].append(i*n + j + n)\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if degree[i][j] == 0:\n",
    "                    search = link[i][j]\n",
    "                    d = 1\n",
    "                    while search:\n",
    "                        temp = set()\n",
    "                        for idxencode in search:\n",
    "                            x = idxencode // n\n",
    "                            y = idxencode % n\n",
    "                            for enco in link[x][y]:\n",
    "                                temp.add(enco)\n",
    "                        search = list(temp)\n",
    "                        d += 1\n",
    "                    ans = max(ans, d)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        g = [[] for _ in range(m * n)]\n",
    "        deg = [0] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):\n",
    "                    if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:\n",
    "                        g[m * j + i].append(m * y + x)\n",
    "                        deg[m * y + x] += 1\n",
    "\n",
    "        queue = deque([])\n",
    "        for idx, i in enumerate(deg):\n",
    "            if i == 0:\n",
    "                queue.append(idx)\n",
    "\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                for j in g[node]:\n",
    "                    deg[j] -= 1\n",
    "                    if deg[j] == 0:\n",
    "                        queue.append(j)\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        from queue import PriorityQueue\n",
    "        queue=PriorityQueue()\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                queue.put((matrix[i][j],(i,j)))\n",
    "        dp=[[1]*n for i in range(m)]\n",
    "        cnt=m*n\n",
    "        while cnt>0:\n",
    "            value,(x,y)=queue.get()\n",
    "            cnt-=1\n",
    "            for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:\n",
    "                if 0<=x+dx<m and 0<=y+dy<n and matrix[x+dx][y+dy]<matrix[x][y]:\n",
    "                    dp[x][y]=max(dp[x][y],dp[x+dx][y+dy]+1)\n",
    "        return max([max(d) for d in dp ])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIR = [-1, 0, 1, 0, -1]\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix):\n",
    "        self.dx=[0,0,1,-1]       #水平方向偏移量\n",
    "        self.dy=[1,-1,0,0]       #垂直方向偏移量\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        self.dp=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        maxans=0\n",
    "        for i in range(0,m):\n",
    "            for j in range(0,n):\n",
    "                tmp=self.dfs(matrix,m,n,i,j)\n",
    "                if tmp>maxans:maxans=tmp\n",
    "        return maxans\n",
    "    def dfs(self,matrix,m,n,x,y):\n",
    "        if self.dp[x][y]!=0:return self.dp[x][y]\n",
    "        self.dp[x][y]=1\n",
    "        maxlen=0\n",
    "        for di in range(0,4):\n",
    "            nx,ny=x+self.dx[di],y+self.dy[di]\n",
    "            if nx<0 or nx>=m or ny<0 or ny>=n:continue\n",
    "            if matrix[nx][ny]<=matrix[x][y]:continue\n",
    "            tmp=self.dfs(matrix,m,n,nx,ny)\n",
    "            if tmp>maxlen:maxlen=tmp\n",
    "        self.dp[x][y]+=maxlen\n",
    "        return self.dp[x][y]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = None\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        self.res = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))] \n",
    "        r = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                self.dfs(matrix, i, j)\n",
    "                r = max(r, self.res[i][j])\n",
    "        return r\n",
    "    def dfs(self, matrix, i, j):\n",
    "        if self.res[i][j] != 0:\n",
    "            return self.res[i][j]\n",
    "        if i > 0  and matrix[i - 1][j] > matrix[i][j]:\n",
    "            left = self.dfs(matrix, i - 1, j)\n",
    "        else:\n",
    "            left = 0\n",
    "\n",
    "        if j > 0 and matrix[i][j - 1] > matrix[i][j]:\n",
    "            top = self.dfs(matrix, i, j - 1)\n",
    "        else:\n",
    "            top = 0\n",
    "\n",
    "        if j < len(matrix[0]) - 1 and matrix[i][j + 1] > matrix[i][j]:\n",
    "            right = self.dfs(matrix, i, j + 1)\n",
    "        else:\n",
    "            right = 0\n",
    "\n",
    "        if i < len(matrix) - 1 and matrix[i + 1][j] > matrix[i][j]:\n",
    "            down = self.dfs(matrix, i + 1, j)\n",
    "        else:\n",
    "            down = 0\n",
    "\n",
    "        self.res[i][j] = 1 + max(top, down, left, right)\n",
    "        return 1 + max(top, down, left, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "\n",
    "        self.dp = [[0]*n for _ in range(m)]\n",
    "        def traverse(i,j,last):\n",
    "            if i<0 or i>=m or j>=n or j<0:\n",
    "                return 0\n",
    "\n",
    "            cur = matrix[i][j]\n",
    "            if cur>last:\n",
    "                if self.dp[i][j] != 0:\n",
    "                    return self.dp[i][j]\n",
    "                res = 1+max(traverse(i,j-1,cur),traverse(i,j+1,cur),traverse(i-1,j,cur),traverse(i+1,j,cur))\n",
    "                self.dp[i][j] = res\n",
    "                return res\n",
    "            else:\n",
    "                return 0\n",
    "        ans = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans,traverse(i,j,float('-inf')))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        def dfs(matrix, m, n, store, y, x) -> int:\n",
    "            if store[y][x] is not None:\n",
    "                return store[y][x]\n",
    "            temp_1, temp_2, temp_3, temp_4 = 0, 0, 0, 0\n",
    "            if x + 1 < n:\n",
    "                if matrix[y][x + 1] > matrix[y][x]:\n",
    "                    temp_1 = dfs(matrix, m, n, store, y, x + 1)\n",
    "            if x - 1 >= 0:\n",
    "                if matrix[y][x - 1] > matrix[y][x]:\n",
    "                    temp_2 = dfs(matrix, m, n, store, y, x - 1)\n",
    "            if y + 1 < m:\n",
    "                if matrix[y + 1][x] > matrix[y][x]:\n",
    "                    temp_3 = dfs(matrix, m, n, store, y + 1, x)\n",
    "            if y - 1 >= 0:\n",
    "                if matrix[y - 1][x] > matrix[y][x]:\n",
    "                    temp_4 = dfs(matrix, m, n, store, y - 1, x)\n",
    "            store[y][x] = max(temp_1, temp_2, temp_3, temp_4) + 1\n",
    "            return store[y][x]\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        store = []\n",
    "        res = 1\n",
    "        for i in range(m):\n",
    "            store.append([None] * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                store[i][j] = dfs(matrix, m, n, store, i, j)\n",
    "                res = max(res, store[i][j])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        memo = [[1] * n for _ in range(m)]\n",
    "        self.best = 1\n",
    "\n",
    "        def helper(x, y):\n",
    "            for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "                nx, ny = dx + x, dy + y\n",
    "\n",
    "                if not (0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[x][y]):\n",
    "                    continue\n",
    "\n",
    "                if memo[nx][ny] > memo[x][y]:\n",
    "                    continue\n",
    "                \n",
    "                memo[nx][ny] = memo[x][y] + 1\n",
    "                self.best = max(self.best, memo[nx][ny])\n",
    "                helper(nx, ny)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                helper(i, j)\n",
    "\n",
    "        return self.best\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef longestIncreasingPath(self, matrix: List[List[int]]) -> int:    \n",
    "\t\tm,n=len(matrix),len(matrix[0])\n",
    "\t\td=[[0,1],[0,-1],[-1,0],[1,0]]\n",
    "\t\tpath=[[-1 for j in range(n)] for i in range(m)]\n",
    "\t\tdef dfs(x,y):\n",
    "\t\t\tif path[x][y]!=-1:\n",
    "\t\t\t\treturn path[x][y]\n",
    "\t\t\tmax_path=0\n",
    "\t\t\tfor i,j in d:\n",
    "\t\t\t\t_x,_y=x+i,y+j\n",
    "\t\t\t\tif _x<0 or _x>=m or _y<0 or _y>=n or matrix[_x][_y] <= matrix[x][y]:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tmax_path=max(max_path,dfs(_x,_y))\n",
    "\t\t\tpath[x][y]=max_path+1\n",
    "\t\t\treturn max_path+1\n",
    "\n",
    "\t\tans=0\n",
    "\t\tfor i in range(m):\n",
    "\t\t\tfor j in range(n):\n",
    "\t\t\t\tif path[i][j]==-1:\n",
    "\t\t\t\t\tans=max(ans,dfs(i,j))\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        rows = len(matrix)\n",
    "        columns = len(matrix[0])\n",
    "        longest_increasing_path_matrix = [0] * rows\n",
    "        for index in range(rows):\n",
    "            longest_increasing_path_matrix[index] = [0] * columns\n",
    "        answer = 0\n",
    "        for row in range(rows):\n",
    "            for column in range(columns):\n",
    "                answer = max(answer, dfs(matrix, longest_increasing_path_matrix, rows, columns, row, column, -1))\n",
    "        return answer\n",
    "\n",
    "def dfs(matrix, longest_increasing_path_matrix, rows, columns, row, column, pre_val):\n",
    "    if row < 0 or row >= rows or column < 0 or column >= columns or pre_val >= matrix[row][column]:\n",
    "        return 0\n",
    "    if longest_increasing_path_matrix[row][column]:\n",
    "        return longest_increasing_path_matrix[row][column]\n",
    "    dy = [0, -1, 0, 1]\n",
    "    dx = [1, 0, -1, 0]\n",
    "    for index in range(4):\n",
    "        longest_increasing_path_matrix[row][column] = max(longest_increasing_path_matrix[row][column], dfs(matrix, longest_increasing_path_matrix, rows, columns, row + dy[index], column + dx[index], matrix[row][column]) + 1)\n",
    "    return longest_increasing_path_matrix[row][column]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestIncreasingPath(self, matrix: list[list[int]]) -> int:\r\n",
    "        m, n = len(matrix), len(matrix[0])\r\n",
    "        dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]\r\n",
    "        visited = [[False] * n for _ in range(m)]\r\n",
    "        res_table = [[1] * n for _ in range(m)]\r\n",
    "        \r\n",
    "        def dfs(x, y):\r\n",
    "            for dir in dirs:\r\n",
    "                next_x, next_y = x + dir[0], y + dir[1]\r\n",
    "                \r\n",
    "                if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:\r\n",
    "                    continue\r\n",
    "                \r\n",
    "                if matrix[next_x][next_y] <= matrix[x][y]:\r\n",
    "                    continue\r\n",
    "\r\n",
    "                \r\n",
    "                if visited[next_x][next_y]:\r\n",
    "                    res_table[x][y] = max(res_table[x][y], res_table[next_x][next_y] + 1) \r\n",
    "                else:\r\n",
    "                    dfs(next_x, next_y)\r\n",
    "                    visited[next_x][next_y] = True\r\n",
    "                    res_table[x][y] = max(res_table[x][y], res_table[next_x][next_y] + 1)\r\n",
    "        \r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if not visited[i][j]:\r\n",
    "                    visited[i][j] = True\r\n",
    "                    dfs(i, j)\r\n",
    "        \r\n",
    "        return max([max(row) for row in res_table])\r\n",
    "                \r\n",
    "                \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dp = [[-1] * n for _ in range(m)]\n",
    "        def dfs(i,j):\n",
    "            if dp[i][j] != -1:\n",
    "                return dp[i][j]\n",
    "            else:\n",
    "                d = 1 \n",
    "                for x,y in [(0,1), (0,-1), (-1,0), (1,0)]:\n",
    "                    new_i, new_j = i+x, y+j \n",
    "                    if 0 <= new_i < len(dp) and 0<=new_j<len(dp[0]) and matrix[new_i][new_j] > matrix[i][j]:\n",
    "                        d = max(d, dfs(new_i, new_j) +1)\n",
    "                dp[i][j] = d \n",
    "            return d \n",
    "        res = 0 \n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if dp[i][j] == -1:\n",
    "                    res = max(res, dfs(i,j))\n",
    "        return res \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIR = [-1, 0, 1, 0, -1]\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param matrix: A matrix\n",
    "    @return: An integer.\n",
    "    \"\"\"\n",
    "    def longestIncreasingPath(self, matrix):\n",
    "        points = []\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                points.append((matrix[i][j], i, j))\n",
    "        points.sort()\n",
    "\n",
    "        parsed_to_index = {}\n",
    "        dp = [1] * len(points)\n",
    "        max_length = 0\n",
    "        for i in range(len(points)):\n",
    "            for j in range(len(DIR) - 1):\n",
    "                x = points[i][1] + DIR[j]\n",
    "                y = points[i][2] + DIR[j + 1]\n",
    "                if (x, y) in parsed_to_index:\n",
    "                    k = parsed_to_index[(x, y)]\n",
    "                    if points[i][0] > points[k][0]:\n",
    "                        dp[i] = max(dp[i], dp[k] + 1)\n",
    "                        max_length = max(max_length, dp[i])\n",
    "            parsed_to_index[(points[i][1], points[i][2])] = i\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        def dfs(x, y):\n",
    "            if dp[x][y] > 0:\n",
    "                return dp[x][y]\n",
    "            mx = 1\n",
    "            if y > 0 and matrix[x][y - 1] > matrix[x][y]:\n",
    "                mx = max(mx, 1 + dfs(x, y - 1))\n",
    "            if y < n - 1 and matrix[x][y + 1] > matrix[x][y]:\n",
    "                mx = max(mx, 1 + dfs(x, y + 1))\n",
    "            if x > 0 and matrix[x - 1][y] > matrix[x][y]:\n",
    "                mx = max(mx, 1 + dfs(x - 1, y))\n",
    "            if x < m - 1 and matrix[x + 1][y] > matrix[x][y]:\n",
    "                mx = max(mx, 1 + dfs(x + 1, y))\n",
    "            dp[x][y] = mx\n",
    "            return mx\n",
    "        mxl = 1\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                mxl = max(mxl, dfs(x, y))\n",
    "        return mxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        dp = [[1]*n for i in range(m)]\n",
    "        read = [[0]*n for i in range(m)]\n",
    "        res = 1\n",
    "\n",
    "        def DFS(x,y,step):\n",
    "            nonlocal res\n",
    "            dire = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "            read[x][y] = 1\n",
    "            maxDire = 0\n",
    "\n",
    "            for xb,yb in dire:\n",
    "                if 0<=x+xb<m and 0<=y+yb<n and matrix[x+xb][y+yb]>matrix[x][y]:\n",
    "                    if not read[x+xb][y+yb]:\n",
    "                        DFS(x+xb,y+yb,step+1)\n",
    "                    maxDire = max(maxDire,dp[x+xb][y+yb])\n",
    "\n",
    "            dp[x][y] += maxDire\n",
    "            res = max(res,dp[x][y])\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not read[i][j]:\n",
    "                    DFS(i,j,1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        dxs = [0, 0, -1, 1]\n",
    "        dys = [1, -1, 0, 0]\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[-1 for _ in range(n)] for _ in range(m)]\n",
    "        vis = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        def dfs(x, y):\n",
    "            if dp[x][y] != -1:\n",
    "                return dp[x][y]\n",
    "            vis[x][y] = 1\n",
    "            cur_max = 0\n",
    "            for dx, dy in zip(dxs, dys):\n",
    "                new_x, new_y = x + dx, y + dy \n",
    "                if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:\n",
    "                    continue\n",
    "                if matrix[new_x][new_y] <= matrix[x][y]:\n",
    "                    continue\n",
    "                if vis[new_x][new_y]:\n",
    "                    continue\n",
    "                cur_max = max(cur_max, dfs(new_x, new_y))\n",
    "            dp[x][y] = 1 + cur_max\n",
    "            vis[x][y] = 0\n",
    "            return dp[x][y]\n",
    "        max_step = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                max_step = max(dfs(i, j), max_step)\n",
    "        return max_step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        memo = {}\n",
    "\n",
    "        def dfs(x:int, y:int, pre:int) -> int:\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                return 0\n",
    "            \n",
    "            if matrix[x][y] <= pre:\n",
    "                return 0 \n",
    "            \n",
    "            if (x, y) in memo:\n",
    "                return memo[(x, y)]\n",
    "            \n",
    "            cur = matrix[x][y]\n",
    "\n",
    "            res = max(dfs(x-1, y, cur), dfs(x+1, y, cur), dfs(x, y-1, cur), dfs(x, y+1, cur)) + 1\n",
    "            memo[(x, y)] = res\n",
    "\n",
    "            return res \n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i, j, float('-inf')))\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        memo = defaultdict(int)\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        def dfs(row, col, m, n):\n",
    "            step = 0\n",
    "            for i, j in (row+1, col), (row-1, col), (row, col+1), (row, col-1):\n",
    "                if 0<=i<m and 0<=j<n and matrix[i][j] > matrix[row][col]:\n",
    "                    if (i, j) in memo:\n",
    "                        step = max(step, memo[(i, j)])\n",
    "                    else:\n",
    "                        step = max(dfs(i, j, m, n), step)\n",
    "            memo[(row, col)] = step + 1\n",
    "            return step+1\n",
    "                \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i, j) not in memo:\n",
    "                    dfs(i, j, m, n)\n",
    "        return sorted(memo.values())[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        vis = {}\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        def dfs(i, j):\n",
    "            if (i,j) in vis:\n",
    "                return vis[(i,j)]\n",
    "            curr_val = matrix[i][j]\n",
    "            temp = 1\n",
    "            for x, y in [(-1, 0), (1, 0), (0, -1), (0,1)]:\n",
    "                new_x, new_y = x+i, y+j\n",
    "                if 0 <= new_x < m and 0 <= new_y < n and matrix[new_x][new_y] > curr_val:\n",
    "                    temp = max(temp, 1+dfs(new_x, new_y))\n",
    "            vis[(i,j)] = temp\n",
    "            return vis[(i,j)]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i,j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dx,dy =[-1,1,0,0],[0,0,-1,1]\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "        if not matrix:\n",
    "            return 0\n",
    "\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int,j:int):\n",
    "            \n",
    "            ans=1\n",
    "            for k in range(4):\n",
    "                nx ,ny=dx[k]+i,dy[k]+j \n",
    "                if nx <0 or nx>=m or ny<0 or ny>=n:\n",
    "                    continue\n",
    "                if matrix[nx][ny] > matrix[i][j]:\n",
    "                    ans = max(ans,dfs(nx,ny)+1)\n",
    "            return ans \n",
    "\n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ret= max(ret,dfs(i,j))\n",
    "        return ret  \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix),len(matrix[0])\n",
    "        \n",
    "        mem = {}\n",
    "        def dfs(x, y):\n",
    "            if (x,y) in mem:\n",
    "                return mem[(x, y)]\n",
    "            longest = 0\n",
    "            for dir in [(1,0),(-1,0),(0,1),(0,-1)]:\n",
    "                xx, yy = x+dir[0],y+dir[1]\n",
    "                if 0<=xx<m and 0<=yy<n and matrix[xx][yy]>matrix[x][y]:\n",
    "                    longest=max(longest, dfs(xx, yy))\n",
    "            mem[(x, y)] = 1+longest\n",
    "            return 1+longest\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i, j))\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(row: int, column: int) -> int:\n",
    "            best = 1\n",
    "            for dx, dy in DIRS:\n",
    "                newRow, newColumn = row + dx, column + dy\n",
    "                if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[row][column]:\n",
    "                    best = max(best, dfs(newRow, newColumn) + 1)\n",
    "            return best\n",
    "\n",
    "        ans = 0\n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "        if not matrix: return 0\n",
    "        cache = {} # 用于缓存结果的字典\n",
    "\n",
    "        def is_legal(x, y):\n",
    "            return 0 <= x < m and 0 <= y < n\n",
    "        \n",
    "        # @cache\n",
    "        def helper(x, y):\n",
    "            if (x, y) in cache:\n",
    "                return cache[(x, y)]  # 如果结果已缓存，直接返回\n",
    "\n",
    "            local_max = 1\n",
    "            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if is_legal(new_x, new_y) and matrix[new_x][new_y] > matrix[x][y]:\n",
    "                    local_max = max(local_max, helper(new_x, new_y) + 1)\n",
    "            cache[(x, y)] = local_max\n",
    "            return local_max\n",
    "            \n",
    "           \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                local_max = helper(i, j)\n",
    "                res = max(local_max, res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        Dir = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(x,y):\n",
    "            res = 1\n",
    "            for a,b in Dir:\n",
    "                nx = x+a\n",
    "                ny = y+b\n",
    "                if 0<= nx<m and 0<= ny <n and matrix[nx][ny]>matrix[x][y]:\n",
    "                    res = max(res,1+dfs(nx, ny))\n",
    "            return res\n",
    "\n",
    "\n",
    "        ans = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans ,dfs(i,j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def search(i, j) -> int:    \n",
    "            \"\"\"\n",
    "            return longest increasing path till this cell \n",
    "            \"\"\"\n",
    "            res = 0 # initilized for subroute path before(i, j)\n",
    "            for di, dj in dirs:\n",
    "                ni, nj = i + di, j + dj\n",
    "                if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] < matrix[i][j]:\n",
    "                    res = max(search(ni, nj), res)\n",
    "\n",
    "            return res + 1  # adding current cell in the path\n",
    "\n",
    "        longest = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                longest = max(search(i, j), longest)\n",
    "        \n",
    "        return longest\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(row: int, column: int) -> int:\n",
    "            best = 1\n",
    "            for dx, dy in Solution.DIRS:\n",
    "                newRow, newColumn = row + dx, column + dy\n",
    "                if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[row][column]:\n",
    "                    best = max(best, dfs(newRow, newColumn) + 1)\n",
    "            return best\n",
    "\n",
    "        ans = 0\n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(row, colum):\n",
    "            best = 1\n",
    "            for dx, dy in Solution.DIRS:\n",
    "                tx, ty = row + dx, colum + dy\n",
    "                if 0 <= tx < rows and 0 <= ty < colums and matrix[tx][ty] > matrix[row][colum]:\n",
    "                    best = max(best, dfs(tx, ty) + 1)\n",
    "            return best\n",
    "\n",
    "        ans = 0\n",
    "        rows, colums = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(colums):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(row: int, column: int) -> int:\n",
    "            best = 1\n",
    "            for dx, dy in Solution.DIRS:\n",
    "                newRow, newColumn = row + dx, column + dy\n",
    "                if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[row][column]:\n",
    "                    best = max(best, dfs(newRow, newColumn) + 1)\n",
    "            return best\n",
    "\n",
    "        ans = 0\n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        from functools import cache\n",
    "        dirs = [(1,0), (-1,0), (0,1), (0,-1)]\n",
    "        @cache\n",
    "        def rec(x, y):\n",
    "            res = 1\n",
    "            for a, b in dirs:\n",
    "                nx = x+a\n",
    "                ny = y+b\n",
    "                if 0<=nx<m and 0<=ny<n and matrix[nx][ny] > matrix[x][y]:\n",
    "                    res = max(res, 1+rec(nx, ny))\n",
    "            return res\n",
    "\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "               res = max(res, rec(i,j))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(row: int, column: int) -> int:\n",
    "            best = 1\n",
    "            for dx, dy in Solution.DIRS:\n",
    "                newRow, newColumn = row + dx, column + dy\n",
    "                if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[row][column]:\n",
    "                    best = max(best, dfs(newRow, newColumn) + 1)\n",
    "            return best\n",
    "\n",
    "        ans = 0\n",
    "        rows, columns = len(matrix), len(matrix[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(columns):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, a: List[List[int]]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            ans = 1\n",
    "            for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                if 0 <= x < len(a) and 0 <=y <len(a[0]) and a[x][y] > a[i][j]:\n",
    "                    ans = max(ans, f(x, y)+1)\n",
    "            return ans\n",
    "        return max(f(i, j) for i in range(len(a)) for j in range(len(a[0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        \n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            best = 1\n",
    "            for add_row, add_col in ((0,1), (1, 0), (0, -1), (-1, 0)):\n",
    "                new_row = i + add_row\n",
    "                new_col = j + add_col\n",
    "                if 0 <= new_row < m and 0 <= new_col < n and matrix[new_row][new_col] > matrix[i][j]:\n",
    "                    best = max(best, dfs(new_row, new_col) + 1)\n",
    "            return best\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i, j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            ans = 1\n",
    "            for x,y in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                if 0 <= x and x < m and 0 <= y and y < n and matrix[i][j] < matrix[x][y]:\n",
    "                    res = dfs(x,y) + 1\n",
    "                    ans = max(res,ans)\n",
    "            return ans\n",
    "\n",
    "        anss = -1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                anss = max(dfs(i,j),anss)\n",
    "        return anss\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i:int, j:int) ->int:\n",
    "            cur_len = 1\n",
    "\n",
    "            for (x, y) in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if 0<=x and x<m and 0<=y and y<n and matrix[x][y]>matrix[i][j]:\n",
    "                    cur_len = max(cur_len, dfs(x,y)+1)\n",
    "            return cur_len\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i, j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "        height, width = len(matrix), len(matrix[0])\n",
    "\n",
    "        out_cnt = [[0] * width for _ in range(height)]\n",
    "        in_edges = collections.defaultdict(list)\n",
    "\n",
    "        direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        queue = []\n",
    "        path = [[0] * width for _ in range(height)]\n",
    "\n",
    "        for i in range(height):\n",
    "            for j in range(width):\n",
    "                for dx, dy in direct:\n",
    "                    nx, ny = i+dx, j+dy\n",
    "                    if 0 <= nx < height and 0 <= ny < width and matrix[nx][ny] > matrix[i][j]:\n",
    "                        out_cnt[i][j] += 1\n",
    "                        in_edges[(nx, ny)].append((i, j))\n",
    "                if out_cnt[i][j] == 0:\n",
    "                    queue.append((i, j))\n",
    "                    path[i][j] = 1\n",
    "        \n",
    "        ans = 1\n",
    "        while queue:\n",
    "            i, j = queue.pop(0)\n",
    "            edges = in_edges[(i, j)]\n",
    "            for x, y in edges:\n",
    "                path[x][y] = max(path[x][y], path[i][j] + 1)\n",
    "                ans = max(ans, path[x][y])\n",
    "                out_cnt[x][y] -= 1\n",
    "                if out_cnt[x][y] == 0:\n",
    "                    queue.append((x, y))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, a: List[List[int]]) -> int:\n",
    "        m , n = len(a), len(a[0])\n",
    "        dp = [[0 for j in range(n)] for i in range(m)]\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if dp[i][j]>0: return dp[i][j]\n",
    "            dp[i][j] = 1\n",
    "            for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                if 0 <= x < m and 0 <=y <n and a[x][y] > a[i][j]:\n",
    "                    dp[i][j] = max(dp[i][j], f(x, y)+1)\n",
    "            return dp[i][j]\n",
    "        return max(f(i, j) for i in range(m) for j in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        store = [[-1]*n for _ in range(m)]\n",
    "        visit = [[False]*n for _ in range(m)]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def move(i,j):\n",
    "                # if visit[i][j]:\n",
    "                #     return 0\n",
    "                # if store[i][j]!=-1:\n",
    "                #     return store[i][j]\n",
    "                res = 1\n",
    "                num = matrix[i][j]\n",
    "                visit[i][j] = True\n",
    "                if i+1<m and num<matrix[i+1][j]:\n",
    "                    res = max(res, move(i+1,j)+1)\n",
    "                if i-1>=0 and num<matrix[i-1][j]:\n",
    "                    res = max(res, move(i-1,j)+1)\n",
    "                if j+1<n and num<matrix[i][j+1]:\n",
    "                    res = max(res, move(i,j+1)+1)\n",
    "                if j-1>=0 and num<matrix[i][j-1]:\n",
    "                    res = max(res, move(i,j-1)+1)\n",
    "                visit[i][j] = False\n",
    "                # store[i][j] = res\n",
    "                return res\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                v = move(i,j)\n",
    "                ans = max(ans,v)\n",
    "                print(i,j,v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        point_to = {}\n",
    "        point_by = {}\n",
    "        for I in range(m*n):\n",
    "            point_to[I] = []\n",
    "            point_by[I] = []\n",
    "        for I in range(m*n):\n",
    "            i,j = I//n, I%n\n",
    "            x = matrix[i][j]\n",
    "            if i > 0 and matrix[i-1][j] > x:\n",
    "                point_to[I].append(I-n)\n",
    "                point_by[I-n].append(I)\n",
    "            if i < m-1 and matrix[i+1][j] > x:\n",
    "                point_to[I].append(I+n)\n",
    "                point_by[I+n].append(I)\n",
    "            if j > 0 and matrix[i][j-1] > x:\n",
    "                point_to[I].append(I-1)\n",
    "                point_by[I-1].append(I)\n",
    "            if j < n-1 and matrix[i][j+1] > x:\n",
    "                point_to[I].append(I+1)\n",
    "                point_by[I+1].append(I)\n",
    "        #print(point_to)\n",
    "        #print(point_by)\n",
    "        L = 0\n",
    "        while point_to:\n",
    "            removed = []\n",
    "            for a in point_to:\n",
    "                if not point_to[a]:\n",
    "                    removed.append(a)\n",
    "            for a in removed:\n",
    "                del point_to[a]\n",
    "                for b in point_by[a]:\n",
    "                    point_to[b].remove(a)\n",
    "            L += 1\n",
    "            #print('L =',L)\n",
    "            #print(point_to)\n",
    "            #print(point_by)\n",
    "        return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if (i, j) in cache:\n",
    "                return cache[(i, j)]\n",
    "            dist = 1\n",
    "            for d in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < R and 0 <= y < C and matrix[x][y] > matrix[i][j]:\n",
    "                    dist = max(dist, 1+dfs(x,y))\n",
    "            cache[(i, j)] = dist\n",
    "            return dist\n",
    "        \n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                res = max(res, dfs(i, j))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        \n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            self.visit[i][j] = True\n",
    "            neighbor = [\n",
    "                [i - 1, j],\n",
    "                [i + 1, j],\n",
    "                [i, j - 1],\n",
    "                [i, j + 1],\n",
    "            ]\n",
    "            res = 1\n",
    "            for px, py in neighbor:\n",
    "                if 0 <= px < m and 0 <= py < n and not self.visit[px][py]:\n",
    "                    if matrix[i][j] < matrix[px][py]:\n",
    "                        res = max(res, dfs(px, py) + 1)\n",
    "                        self.visit[px][py] = False\n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.visit = [[False] * n for _ in range(m)]                \n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        r, c = len(matrix), len(matrix[0])\n",
    "\n",
    "        outdegree = {}\n",
    "        # indegree = {}\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                outdegree[(i,j)] = 0\n",
    "                # indegree[(i,j)] = 0\n",
    "\n",
    "        mp = collections.defaultdict(list)\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                for di, dj in [(1, 0), (0, 1)]:\n",
    "                    newi, newj = i + di, j + dj\n",
    "\n",
    "                    if 0 <= newi < r and 0 <= newj < c:\n",
    "                        if matrix[newi][newj] > matrix[i][j]:\n",
    "                            mp[(newi, newj)].append((i, j))\n",
    "                            outdegree[(i, j)] += 1\n",
    "                            # indegree[(newi, newj)] += 1\n",
    "                        elif matrix[i][j] > matrix[newi][newj]:\n",
    "                            mp[(i, j)].append((newi, newj))\n",
    "                            outdegree[(newi, newj)] += 1\n",
    "                            # indegree[(i, j)] += 1\n",
    "        \n",
    "\n",
    "        queue = collections.deque([])\n",
    "\n",
    "        for key, val in outdegree.items():\n",
    "            if val == 0:\n",
    "                queue.append(key)\n",
    "        step = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                ii, jj = queue.popleft()\n",
    "                if (ii, jj) in mp:\n",
    "                    for prei, prej in mp[(ii, jj)]:\n",
    "                        outdegree[(prei, prej)] -= 1\n",
    "\n",
    "                        if outdegree[(prei, prej)] == 0:\n",
    "                            queue.append((prei, prej))\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return step\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        DIRS = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "\n",
    "        map = {}\n",
    "\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            if (i ,j) in map:\n",
    "                return map[(i, j)]\n",
    "\n",
    "            if not (0 <= i < m and 0 <= j < n):\n",
    "                map[(i, j)] = 0\n",
    "                return 0\n",
    "\n",
    "            tmp = 1\n",
    "            for each in DIRS:\n",
    "                x = i + each[0]\n",
    "                y = j + each[1]\n",
    "                if 0 <= x < m and 0 <= y < n and matrix[i][j] < matrix[x][y]:\n",
    "                    tmp = max(tmp, dfs(x, y) + 1)\n",
    "            map[(i, j)] = tmp\n",
    "            return tmp\n",
    "        \n",
    "        res = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i, j))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        dir=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        n=len(matrix)\n",
    "        m=len(matrix[0])\n",
    "        ans=0\n",
    "        @cache\n",
    "        def dfs(x,y):\n",
    "            now=1\n",
    "            for dx,dy in dir:\n",
    "                if x+dx>=0 and y+dy>=0 and x+dx<n and y+dy<m:\n",
    "                    if matrix[x+dx][y+dy]>matrix[x][y]:\n",
    "                        now=max(now,dfs(dx+x,dy+y)+1)\n",
    "            return now\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans=max(ans,dfs(i,j))\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        dir=[[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        n=len(matrix)\n",
    "        m=len(matrix[0])\n",
    "        ans=0\n",
    "        @cache\n",
    "        def dfs(x,y):\n",
    "            now=1\n",
    "            for dx,dy in dir:\n",
    "                if x+dx>=0 and y+dy>=0 and x+dx<n and y+dy<m:\n",
    "                    if matrix[x+dx][y+dy]>matrix[x][y]:\n",
    "                        temp =dfs(dx+x,dy+y)\n",
    "                        now=now if temp+1<now else temp+1\n",
    "            return now\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                temp =dfs(i,j)\n",
    "                ans=ans if  temp < ans else  temp \n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        print(matrix)\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        moves = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        \n",
    "        mem = {}\n",
    "        def dfs(i, j, nums):\n",
    "            nonlocal mem\n",
    "            if (i, j) in mem:\n",
    "                return mem[(i, j)]\n",
    "\n",
    "            t = 1\n",
    "            for (m_x, m_y) in moves:\n",
    "                new_i = i + m_x\n",
    "                new_j = j + m_y\n",
    "                if 0 <= new_i < row and 0 <= new_j < col and nums[i][j] < nums[new_i][new_j]:\n",
    "                    t = max(t, 1 + dfs(new_i, new_j, nums))\n",
    "\n",
    "            mem[(i, j)] = t\n",
    "            return t\n",
    "\n",
    "        best = 1\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                t = dfs(i, j, matrix)\n",
    "                print(t)\n",
    "                best = max(best, t)\n",
    "        return best\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(x,y):\n",
    "            \"\"\"Return the length of the path starting from (x,y)\"\"\"\n",
    "            offsets = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "            best = 1\n",
    "            for x_offset,y_offset in offsets:\n",
    "                x_new = x+x_offset\n",
    "                y_new = y+y_offset\n",
    "                if not 0<=x_new<M:\n",
    "                    continue\n",
    "                if not 0<=y_new<N:\n",
    "                    continue\n",
    "                if not matrix[x_new][y_new]>matrix[x][y]:\n",
    "                    continue\n",
    "                best = max(best, 1+dfs(x_new,y_new))\n",
    "\n",
    "            return best\n",
    "\n",
    "        best = 0\n",
    "        M = len(matrix)\n",
    "        N = len(matrix[0])\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                best = max(best, dfs(i,j))\n",
    "        \n",
    "        return best\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        note = {}\n",
    "\n",
    "        def ValidNextPos(lastPos):\n",
    "            offsets = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "            validPos = []\n",
    "            for offset in offsets:\n",
    "                nextPos = (lastPos[0]+offset[0], lastPos[1]+offset[1])\n",
    "                if nextPos[0] >= 0 and nextPos[0] < m and nextPos[1] >= 0 and nextPos[1] < n and matrix[nextPos[0]][nextPos[1]] > matrix[lastPos[0]][lastPos[1]]:\n",
    "                    validPos.append(nextPos)                \n",
    "            return validPos\n",
    "\n",
    "        def dfs(lastPos):\n",
    "            validPos = ValidNextPos(lastPos)\n",
    "            if len(validPos) == 0:\n",
    "                return 1\n",
    "            local_max_length = 1\n",
    "            for pos in validPos:\n",
    "                if pos in note:\n",
    "                    length = note[pos]\n",
    "                else:   \n",
    "                    length = dfs(pos)\n",
    "                    note[pos] = length\n",
    "                if length + 1 > local_max_length:\n",
    "                    local_max_length = length + 1\n",
    "            return local_max_length\n",
    "        \n",
    "\n",
    "        self.max_length = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pos = (i, j)\n",
    "                if pos in note:\n",
    "                    length = note[pos]\n",
    "                else:\n",
    "                    length = dfs(pos)\n",
    "                    note[pos] = length\n",
    "                if length > self.max_length:\n",
    "                    self.max_length = length\n",
    "        return self.max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "        \n",
    "        # 从 (i, j) 出发的最长递增路径长度\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            ans = 1\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                # 如果是递增的，更新答案\n",
    "                if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[x][y]:\n",
    "                    ans = max(ans, dfs(nx, ny)+1)\n",
    "            return ans\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i, j))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        def helper(i, j):\n",
    "            if (i, j) in dic:\n",
    "                return dic[(i,j)]\n",
    "            step = 1\n",
    "            for d in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < R and 0 <= y < C and matrix[x][y] > matrix[i][j]:\n",
    "                    step = max(step, helper(x, y) + 1)\n",
    "            dic[(i, j)] = step\n",
    "            return step\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                res = max(res, helper(i, j))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\r\n",
    "        @lru_cache(None)\r\n",
    "        def dfs(i, j):\r\n",
    "            best = 1\r\n",
    "            for x, y in dirs:\r\n",
    "                if 0 <= i + x < m and 0 <= j + y < n and matrix[i+x][j+y] > matrix[i][j]:\r\n",
    "                    best = max(best, dfs(i+x, j+y) + 1)\r\n",
    "            return best\r\n",
    "        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]\r\n",
    "        m, n = len(matrix), len(matrix[0])\r\n",
    "        res = 0\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                res = max(res, dfs(i, j))\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        flag = [[True]*n for _ in range(m)]\n",
    "        memo = dict()\n",
    "        def dfs(i,j,pre):\n",
    "            if not 0<=i<m or not 0<=j<n or not flag[i][j] or matrix[i][j]<=pre:\n",
    "                # memo[(i,j)] = 0\n",
    "                return 0\n",
    "            if (i,j) in memo:return memo[(i,j)]\n",
    "            flag[i][j] = False\n",
    "            cur = matrix[i][j]\n",
    "            left, top, right, bot = dfs(i,j-1,cur), dfs(i-1,j,cur), dfs(i,j+1,cur), dfs(i+1,j,cur)\n",
    "            flag[i][j] = True\n",
    "            memo[(i,j)] = max(left, top, right, bot) + 1\n",
    "            return memo[(i,j)] \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, dfs(i,j,-1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix or not matrix[0]: return 0\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            best = 1\n",
    "            if j + 1 < n and matrix[i][j + 1] > matrix[i][j]:\n",
    "                best = max(best, dfs(i, j + 1) + 1)\n",
    "\n",
    "            if j - 1 >= 0 and matrix[i][j - 1] > matrix[i][j]:\n",
    "                best = max(best, dfs(i, j - 1) + 1)\n",
    "\n",
    "            if i + 1 < m and matrix[i + 1][j] > matrix[i][j]:\n",
    "                best = max(best, dfs(i + 1, j) + 1)\n",
    "\n",
    "            if i - 1 >= 0 and matrix[i - 1][j] > matrix[i][j]:\n",
    "                best = max(best, dfs(i - 1, j) + 1)\n",
    "\n",
    "            return best \n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = max(ans, dfs(i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def backtrack(i,j):\n",
    "            ans =1\n",
    "            for d in dirc:\n",
    "                x = i+d[0]\n",
    "                y = j+d[1]\n",
    "                if x<0 or x>=m or y<0 or y>=n:\n",
    "                    continue\n",
    "                if matrix[x][y] >matrix[i][j]:\n",
    "                    ans = max(ans,backtrack(x,y)+1)\n",
    "            return ans\n",
    "\n",
    "\n",
    "        dirc = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res,backtrack(i,j))\n",
    "                # used.remove((i,j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        @cache\n",
    "        def backtrack(i: int, j: int) -> int:\n",
    "\n",
    "            path_len = 1\n",
    "            cur = matrix[i][j]\n",
    "            for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "                x, y = i + dx, j + dy\n",
    "                if x >= 0 and x < m and y >= 0 and y < n:\n",
    "                    if cur < matrix[x][y]:\n",
    "                        path_len = max(path_len, 1 + backtrack(x, y))\n",
    "\n",
    "            return path_len\n",
    "\n",
    "        res = 1\n",
    "        for a in range(m):\n",
    "            for b in range(n):\n",
    "                res = max(res, backtrack(a, b))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        dires = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            ans = 1\n",
    "            for dire in dires:\n",
    "                x = i+dire[0]\n",
    "                y = j+dire[1]\n",
    "                if x<0 or y<0 or x>m-1 or y>n-1 or matrix[x][y] <=matrix[i][j]:\n",
    "                    continue\n",
    "                ans = max(ans,dfs(x,y)+1)\n",
    "            return ans\n",
    "        res = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res,dfs(i,j))\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        d = ((0,-1), (0,1),(-1,0),(1,0))\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            ret = 0\n",
    "            for di, dj in d:\n",
    "                ii, jj = i+di, j+dj\n",
    "                if 0 <= ii < n and 0 <= jj < m:\n",
    "                    if matrix[i][j] < matrix[ii][jj]:\n",
    "                        ret = max(ret, dfs(ii,jj))\n",
    "            \n",
    "            return ret + 1\n",
    "\n",
    "\n",
    "        return max(dfs(i,j) for i in range(n) for j in range(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        R, C = len(matrix), len(matrix[0])\n",
    "        visited = [[False] * C for _ in range(R)]\n",
    "        def helper(i, j):\n",
    "            if (i, j) in dic:\n",
    "                return dic[(i,j)]\n",
    "            visited[i][j] = True\n",
    "            step = 1\n",
    "            for d in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < R and 0 <= y < C and matrix[x][y] > matrix[i][j] and not visited[x][y]:\n",
    "                    step = max(step, helper(x, y) + 1)\n",
    "            visited[i][j] = False\n",
    "            dic[(i, j)] = step\n",
    "            return step\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                res = max(res, helper(i, j))\n",
    "        \n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
